Link to this headingElliptic Curve Diffie Hellman (ECDH)

  • ECDH Is almost the exact same as regular Diffie-Hellman. But instead of G^a its G*a.
  • Works on the principle that it is hard to find G*a*b when only knowing G*a and G*b

Hands-on: X25519 Key Exchange

Link to this headingImplementation

from ecc_lib import * if __name__ == '__main__': #### Setup #User1 Generates their Private Public KeyPair privateKey1, public_point1 = generate_KeyPair(Curve25519_Generator_Point) print(privateKey1, public_point1) #User2 Generates their Private Public KeyPair privateKey2, public_point2 = generate_KeyPair(Curve25519_Generator_Point) print(privateKey2, public_point2) #### Exchange Data # User1 recives User2's Public Key # User2 recives User1's Public Key #### Key Generation #User1 Takes their Private Key and Multiplies it by User2's Public Key user1_shared_key = privateKey1 * public_point2 #User2 Takes their Private Keu and multiplies it by User1's Public Key user2_shared_key = privateKey2 * public_point1 #### Assurange that the shared key is the same #print(user2_shared_key, user1_shared_key) assert user1_shared_key == user2_shared_key

Link to this headingProtocol Example

Source

  1. User1 and User2 use the same Curve parameters:
    • Lets use y^2 = x^3 + -3 * x + b
  2. For Example let TODO
  3. User1 chooses a secret integer a (e.g. a = 4) and computes G*a
  4. User2 chooses a secret integer a (e.g. a = 3) and computes G*b
  5. Each User exchanges the output to each other
  6. User1 Computes the shared secret using (G*b)*a
  7. User2 Computes the shared secret using (G*a)*b

Link to this headingAttacks

Link to this headingPollard Rho

from ecc_lib import * from Crypto.Util.number import * def func_f(X_i, generator_point, shared_secret): """ To calculate X_(i+1) = f(X_i) :parameters: X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field X_i = (a_i * P) + (b_i * Q) P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field Base point on which ECDLP is defined Q : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field Q = x*P, where `x` is the secret key E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category Elliptic Curve defined as y^2 = x^3 + a*x + b mod p """ curve = generator_point.curve if X_i.x % 3 == 2: # Partition S_1 return curve.add_point(X_i, shared_secret) if X_i.x % 3 == 0: # Partition S_2 return curve.double_point(X_i) if X_i.x % 3 == 1: # Partition S_3 return curve.add_point(X_i, generator_point) else: print("[-] Something's Wrong!") return -1 def func_g(a, generator_point, X_i): """ Calculate a_(i+1) = g(a) :parameters: a : int/long Equivalent to a_i in X_i = a_i*P + b_i*Q P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field Base point on which ECDLP is defined X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field X_i = a_i*P + b_i*Q E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category Elliptic Curve defined as y^2 = x^3 + a*x + b mod p """ n = generator_point.curve.order if X_i.x % 3 == 2: # Partition S_1 return a if X_i.x % 3 == 0: # Partition S_2 return 2*a % n if X_i.x % 3 == 1: # Partition S_3 return (a + 1) % n else: print("[-] Something's Wrong!") return None def func_h(b, generator_point, X_i): """ Calculate a_(i+1) = g(a) :parameters: a : int/long Equivalent to a_i in X_i = a_i*P + b_i*Q P : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field Base point on which ECDLP is defined X_i : sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_finite_field X_i = a_i*P + b_i*Q E : sage.schemes.elliptic_curves.ell_finite_field.EllipticCurve_finite_field_with_category Elliptic Curve defined as y^2 = x^3 + a*x + b mod p """ curve = generator_point.curve if X_i.x % 3 == 2: # Partition S_1 return (b + 1) % curve.order if X_i.x % 3 == 0: # Partition S_2 return 2*b % curve.order if X_i.x % 3 == 1: # Partition S_3 return b else: print("[-] Something's Wrong!") return None def pollardrho(generator_point, shared_secret): order = generator_point.curve.order curve = generator_point.curve for j in range(10): a_i = random.randint(2, order-2) b_i = random.randint(2, order-2) a_2i = random.randint(2, order-2) b_2i = random.randint(2, order-2) X_i = curve.add_point(curve.mul_point(a_i, generator_point), curve.mul_point(b_i, shared_secret)) X_2i = curve.add_point(curve.mul_point(a_2i, generator_point), curve.mul_point(b_2i, shared_secret)) i = 1 while i <= order: # Single Step Calculations a_i = func_g(a_i, generator_point, X_i) b_i = func_h(b_i, generator_point, X_i) X_i = func_f(X_i, generator_point, shared_secret) # Double Step Calculations a_2i = func_g(func_g(a_2i, generator_point, X_2i), generator_point, func_f(X_2i, generator_point, shared_secret)) b_2i = func_h(func_h(b_2i, generator_point, X_2i), generator_point, func_f(X_2i, generator_point, shared_secret)) X_2i = func_f(func_f(X_2i, generator_point, shared_secret), generator_point, shared_secret) if X_i == X_2i: if b_i == b_2i: break assert GCD(b_2i - b_i, order) == 1 return ((a_i - a_2i) * inverse(b_2i - b_i, order)) % order else: i += 1 continue if __name__ == '__main__': """ Anomalous = ShortWeierstrassCurve( name="Anomalous", a=1456400922, b=2005615003, prime_mod=(pow(2,31) - 1), order=(pow(2,31) - 1), #2^5 * 3^7 * 17 * 19 ) x = secure_rand_between(0, Anomalous.order) ys = Anomalous.find_points_by_x(x) Anomalous_Generator_Point = Point(x, ys[0], Anomalous) print(Anomalous_Generator_Point) """ TinyCurve32 = ShortWeierstrassCurve( name="TinyCurve32", a=1745322301, b=130575212, prime_mod=4000001039, order=3999907399, ) Tiny32_Generator_Point = Point(2951351449, 2085375757, TinyCurve32) TinyCurve36 = ShortWeierstrassCurve( name="TinyCurve36", a=10730991330, b=10461429567, prime_mod=50000001637, order=49999749391, ) Tiny36_Generator_Point = Point(39948220728, 46724792678, TinyCurve36) TinyCurve40 = ShortWeierstrassCurve( name="TinyCurve40", a=120982395053, b=42757531213, prime_mod=1000000003571, order=999998469709, ) Tiny40_Generator_Point = Point(923179549631, 952583441553, TinyCurve40) TinyCurve44 = ShortWeierstrassCurve( name="TinyCurve44", a=2172373435844, b=864878753836, prime_mod=9809862296159, order=9809858895373, ) Tiny44_Generator_Point = Point(7573089241231, 4438676127758, TinyCurve44) TinyCurve48 = ShortWeierstrassCurve( name="TinyCurve48", a=18424416311620, b=2813146810101, prime_mod=210548486455921, order=210548502757267, ) Tiny48_Generator_Point = Point(91541889026188, 123287677451334, TinyCurve48) TinyCurve52 = ShortWeierstrassCurve( name="TinyCurve52", a=1130104090562190, b=961750782982658, prime_mod=3093215881333057, order=3093215911838831, ) Tiny52_Generator_Point = Point(2730087332105783, 2918974547317441, TinyCurve52) TinyCurve56 = ShortWeierstrassCurve( name="TinyCurve56", a=17387714570041336, b=14158762040267516, prime_mod=50544702849929377, order=50544703140954961, ) Tiny56_Generator_Point = Point(36182928645730553, 5540583353843909, TinyCurve56) #### Setup #User1 Generates their Private Public KeyPair privateKey1, public_point1 = generate_KeyPair(Tiny32_Generator_Point) print(privateKey1, public_point1) #User2 Generates their Private Public KeyPair privateKey2, public_point2 = generate_KeyPair(Tiny32_Generator_Point) print(privateKey2, public_point2) #### Exchange Data # User1 receives User2's Public Key # User2 receives User1's Public Key #### Key Generation #User1 Takes their Private Key and Multiplies it by User2's Public Key user1_shared_key = privateKey1 * public_point2 #User2 Takes their Private Keu and multiplies it by User1's Public Key user2_shared_key = privateKey2 * public_point1 #### Assurance that the shared key is the same #print(user2_shared_key, user1_shared_key) assert user1_shared_key == user2_shared_key data = pollardrho(Tiny32_Generator_Point, public_point1) print(data) #3735087922 TinyCurve32: x=612544702, y=2755544091 #50009172 TinyCurve32: x=2971908904, y=1911617225 #3735087922 #[Finished in 4.1s]

Link to this headingInvalid Curve Point attack

  • Not testing that both points x and y are on the curve can break the protocol

Link to this headingOptimus Anti-Primes

Since multiplication is commutative, it’s possible that two unrelated pairs of participants could perform an ECDH step and agree on the same shared secret.

This is true for the same reason that 3\times{8} = 4\times{6}, and because your secret key is a random integer.

For this reason, it’s generally unwise to use raw ECDH outputs as encryption keys. Instead, you want to use a cryptographic hash function over the ECDH output and each participants’ public keys to guarantee your symmetric session key is distinct from other pairs.